Digital Signal Processing 1 Basic Concepts and Algorithms Week2

课程主页：https://www.coursera.org/learn/dsp1

这一讲介绍了Signal Processing Meets Vector Space。

希尔伯特空间

希尔伯特空间的三要素

• 向量空间：$H(V, \mathbb{C})$

  • $\forall x,y,z\in V,\alpha, \beta \in \mathbb C$，如下事实成立 $$\begin{array}{l} x+y=y+x \\ (x+y)+z=x+(y+z) \\ \alpha(x+y)=\alpha y+\alpha x \\ (\alpha+\beta) x=\alpha x+\beta x \\ \alpha(\beta x)=(\alpha \beta) x \\ \exists 0 \in V \quad | x+0=0+x=x \\ \forall x \in V, \exists(-x) \quad | \quad x+(-x)=0 \end{array}$$

• 内积：$\langle\cdot, \cdot\rangle: V \times V \rightarrow \mathbb{C}$

  • $\forall x,y,z\in V,\alpha, \beta \in \mathbb C$

    $$\begin{array}{l} \langle\mathbf{x}+\mathbf{y}, \mathbf{z}\rangle=\langle\mathbf{x}, \mathbf{z}\rangle+\langle\mathbf{y}, \mathbf{z}\rangle \\ \langle\mathbf{x}, \mathbf{y}\rangle=\langle\mathbf{y}, \mathbf{x}\rangle^{*} \\ \langle\alpha \mathbf{x}, \mathbf{y}\rangle=\alpha^{*}\langle\mathbf{x}, \mathbf{y}\rangle \\ \langle\mathbf{x}, \alpha \mathbf{y}\rangle=\alpha\langle\mathbf{x}, \mathbf{y}\rangle \\ \langle\mathbf{x}, \mathbf{x}\rangle \geq 0 \\ \langle\mathbf{x}, \mathbf{x}\rangle=0 \Leftrightarrow \mathbf{x}=\mathbf{0}\\ 如果\langle\mathbf{x}, \mathbf{y}\rangle=0,\mathbf x,\mathbf y\neq 0,那么称 \mathbf{x}, \mathbf{y}正交 \end{array}$$

  • 信号的内积

    $$\langle\mathbf{x}, \mathbf{y}\rangle=\sum_{n=0}^{N-1} x^{*}[n] y[n]$$

  • 内积定义了范数：$|\mathbf{x}|=\sqrt{\langle\mathbf{x}, \mathbf{x}\rangle}$

  • 范数定义了距离：$d(\mathbf{x}, \mathbf{y})=|\mathbf{x}-\mathbf{y}|$

    $$\langle\mathbf{x}, \mathbf{y}\rangle=\sum_{n=-\infty}^{\infty} x^{*}[n] y[n]$$

• 完备性

  • 保证极限仍然在希尔伯特空间中

基向量

• 向量空间$H$
• $H$中$K$个向量：$W=\left\{\mathbf{w}^{(k)}\right\}_{k=0,1, \ldots, K-1}$

$W$是$H$的基，如果：

• 对任意$\mathrm x\in H$：

  $$\mathbf{x}=\sum_{k=0}^{K-1} \alpha_{k} \mathbf{w}^{(k)}, \quad \alpha_{k} \in \mathbb{C}$$

• 系数$\alpha_k$唯一

正交基

$$\left\langle\mathbf{w}^{(k)}, \mathbf{w}^{(n)}\right\rangle=0 \text { for } k \neq n$$

标准正交基

$$\left\langle\mathbf{w}^{(k)}, \mathbf{w}^{(n)}\right\rangle=\delta[n-k]$$

Parseval’s Theorem

假设

$$\mathbf{x}=\sum_{k=0}^{K-1} \alpha_{k} \mathbf{w}^{(k)}$$

对于标准正交基，

$$\|\mathbf{x}\|^{2}=\sum_{k=0}^{K-1}\left|\alpha_{k}\right|^{2}$$

最小二乘近似

$\left\{\mathbf{s}^{(k)}\right\}_{k=0,1, \ldots, K-1}$是子空间$S$的标准正交基，那么

$$\mathbf{\hat x}=\sum_{k=0}^{K-1} \langle \mathrm s^{(k)}, \mathrm x\rangle\mathbf{s}^{(k)}$$

是正交投影，即

$$\arg \min _{\mathbf{y} \in S}\|\mathbf{x}-\mathbf{y}\|=\hat{\mathbf{x}}$$

并且$\forall \mathbf y \in S $

$$\langle\mathbf{x}-\hat{\mathbf{x}}, {\mathbf{y}}\rangle=0$$

证明：

将

$$\mathbf{y}=\sum_{k=0}^{K-1} \langle \mathrm s^{(k)}, \mathrm y\rangle\mathbf{s}^{(k)}$$

代入得到：

$$\begin{aligned} \langle\mathbf{x}-\hat{\mathbf{x}}, {\mathbf{y}}\rangle &=\left\langle\mathbf{x},\sum_{k=0}^{K-1} \langle \mathrm s^{(k)}, \mathrm y\rangle\mathbf{s}^{(k)}\right\rangle- \sum_{k=0}^{K-1} \langle \mathrm s^{(k)}, \mathrm x\rangle \langle \mathrm s^{(k)}, \mathrm y\rangle\\ &= \sum_{k=0}^{K-1} \langle \mathrm s^{(k)}, \mathrm x\rangle \langle \mathrm s^{(k)}, \mathrm y\rangle- \sum_{k=0}^{K-1} \langle \mathrm s^{(k)}, \mathrm x\rangle\langle \mathrm s^{(k)}, \mathrm y\rangle\\ &=0 \end{aligned}$$

所以第二个结论正确，接着证明第一个结论：

$$\begin{aligned} \|\mathbf{x}-\mathbf{y}\|^2 &=\langle \mathbf{x}-{\mathbf{y}}, \mathbf{x}-{\mathbf{y}}\rangle\\ &= \langle \mathbf{x}-\hat{\mathbf{x}}+\hat{\mathbf{x}}-{\mathbf{y}}, \mathbf{x}-\hat{\mathbf{x}}+\hat{\mathbf{x}}-{\mathbf{y}}\rangle \\ &= \langle \mathbf{x}-\hat{\mathbf{x}}, \mathbf{x}-\hat{\mathbf{x}}\rangle + \langle \hat{\mathbf{x}}-\mathbf y,\hat{\mathbf{x}}-\mathbf y\rangle+ 2\langle \mathbf{x}-\hat{\mathbf{x}}, \hat{\mathbf{x}}-\mathbf y\rangle\\ &= \|\mathbf{x}-\mathbf{\hat x }\|^2 + \|\mathbf{\hat x }-\mathbf{y}\|^2\\ &\ge \|\mathbf{x}-\mathbf{\hat x }\|^2 \end{aligned}$$

当且仅当下式成立时取等号：

$$\mathrm y = \mathrm {\hat x}$$

Gram-Schmidt正交标准化方法

• 原始集合$\left\{\mathbf{s}^{(k)}\right\}\rightarrow$标准正交集合$\left\{\mathbf{u}^{(k)}\right\}$

方法如下：

在每个步骤$k$

• $\mathbf{p}^{(k)}=\mathbf{s}^{(k)}-\sum_{n=0}^{k-1}\left\langle\mathbf{u}^{(n)}, \mathbf{s}^{(k)}\right\rangle \mathbf{u}^{(n)}$
• $\mathbf{u}^{(k)}=\mathbf{p}^{(k)} /\left|\mathbf{p}^{(k)}\right|$

习题

1

(Difficulty: $\star$ ) Write the value for the inner product $\left\langle\mathbf{v}^{(0)}, \mathbf{v}^{(1)}\right\rangle$ where
$\mathbf{v}^{(0)}=\left[\begin{array}{c}\frac{1}{2} \\ \frac{1}{2} \\ \frac{1}{2} \\ \frac{1}{2}\end{array}\right]$ and $\mathbf{v}^{(1)}=\left[\begin{array}{c}\frac{1}{2} \\ \frac{1}{2} \\ -\frac{1}{2} \\ -\frac{1}{2}\end{array}\right]$

$$\left\langle\mathbf{v}^{(0)}, \mathbf{v}^{(1)}\right\rangle=\frac 1 4 +\frac 1 4 -\frac 1 4 -\frac 1 4 = 0$$

2

(Difficulty: $\star \star)$ Consider the following vectors in $\mathbb{R}^{4}$
$\mathbf v^{(0)}=\left[\begin{array}{c}\frac{1}{2} \\ \frac{1}{2} \\ \frac{1}{2} \\ \frac{1}{2}\end{array}\right], \mathbf{v}^{(1)}=\left[\begin{array}{c}\frac{1}{2} \\ \frac{1}{2} \\ -\frac{1}{2} \\ -\frac{1}{2}\end{array}\right]$ and $\mathbf{v}^{(2)}=\left[\begin{array}{c}\frac{1}{2} \\ -\frac{1}{2} \\ \frac{1}{2} \\ -\frac{1}{2}\end{array}\right]$
You can verify that the vectors are mutually orthogonal and have unit norm.
How many different vectors $\mathbf{v}^{(3)}$ could we find such that $\left\{\mathbf{v}^{(0)}, \mathbf{v}^{(1)}, \mathbf{v}^{(2)}, \mathbf{v}^{(3)}\right\}$ is a full orthonormal
basis in $\mathbb{R}^{4}$ ?

设

$$\mathbf{v}^{(3)} = \left[\begin{array}{c}a\\ b \\ c \\d\end{array}\right]$$

由正交性可得

$$\begin{aligned} a+b+c +d &= 0\\ a+b-c-d &=0\\ a-b+c-d&=0 \end{aligned}$$

所以

$$\begin{aligned} a & =d\\ b& = c\\ a+ b& = 0 \end{aligned}$$

结合

$$\| \mathrm v^{(3)}\|=1$$

可得

$$\mathbf{v}^{(3)} = \pm \left[\begin{array}{c} \frac 1 2\\ -\frac 1 2 \\ -\frac 1 2 \\ \frac 1 2 \end{array}\right]$$

所以答案为2

3

Let $\mathbf{y}=\left[\begin{array}{c}0 \\ -2 \\ 1 \\ -1\end{array}\right]$ what are the expansion coefficients of $\mathbf{y}$ in the basis $\left\{\mathbf{v}_{0}, \mathbf{v}_{1}, \mathbf{v}_{2}, \mathbf{v}_{3}\right\}$ you found in the previous question? Important: Enter your answer as space separated floating point decimal numbers, e.g. the vector y would be entered as:

0.0 -2.0 1.0 -1.0​

答案为，注意提交时需要以小数形式提交

$$\begin{aligned} \alpha_1 &= -1\\ \alpha_2 &= -1\\ \alpha_3 &= 2\\ \alpha_4 &= 0 \end{aligned}$$

答案为-1.0 -1.0 2.0 0.0

4

Which of the following sets form a basis of $\mathbb{R}^{4}$ ?

• $\left\{\mathbf{y}, \mathbf{v}_{0}, \mathbf{v}_{2}, \mathbf{v}_{3}\right\}$
• $\left\{\mathbf{y}, \mathbf{v}_{1}, \mathbf{v}_{2}-\mathbf{v}_{1}, \mathbf{v}_{3}\right\}$
• $\left\{\mathbf{y}, \mathbf{v}_{0}, \mathbf{v}_{1}, \mathbf{v}_{2}\right\}$
• $\left\{\mathbf{y}, \mathbf{y}-\mathbf{v}_{3}, \mathbf{v}_{1}, \mathbf{v}_{3}\right\}$

注意

$$\mathrm y = -\mathrm v_0 -\mathrm v_1 + 2\mathrm v_2$$

所以答案为1,2

5

(Difficulty: $\star$ ) If we represent finite-length signals as vectors in Euclidean space, many operations on signals can be encoded as a matrix-vector multiplication. Consider for example a circular shift in $C^{3}$ : a delay by one (i.e. a right shift) transforms the signal $\mathbf{x}=\left[x_{0} x_{1} x_{2}\right]^{T}$ into $\mathbf{x}^{\prime}=\left[x_{2} x_{0} x_{1}\right]^{T}$ and it can be described by the matrix
$D=\left[\begin{array}{lll}0 & 0 & 1 \\ 1 & 0 & 0 \\ 0 & 1 & 0\end{array}\right]$
so that $\mathbf{x}^{\prime}=D \mathbf{x}$
Determine the matrix $F$ that implements the one-step-difference operator in $C^{3}$ i.e. the operator that transforms a signal $\mathbf{x}$ into $\left[\left(x_{0}-x_{2}\right)\left(x_{1}-x_{0}\right)\left(x_{2}-x_{1}\right)\right]^{T}$
Write the 9 integer matrix coefficients one after the other, row by row and separated by spaces.

$$\begin{aligned} \left[\left(x_{0}-x_{2}\right)\left(x_{1}-x_{0}\right)\left(x_{2}-x_{1}\right)\right]^T &= \mathrm x - \mathrm x\\ &= \mathrm x - D x'\\ &= \left[\begin{matrix}1 & 0 & -1 \\ -1 & 1 & 0 \\ 0 & -1 &1\end{matrix}\right] x \end{aligned}$$

答案为1 0 -1 -1 1 0 0 -1 1

6

(Difficulty $\star$ ) Given the matrix
$A=\left[\begin{array}{llll}0 & 0 & 0 & 1 \\ 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0\end{array}\right]$
compute the matrix $A^{4}$ (i.e. the fourth power of $A$ ).
(Hint: there is a simple way to do that and, if you’ve solved the previous question, it should be obvious).
Write the 16 integer matrix coefficients one after the other, row by row and separated by spaces.

$A$为延迟算子，所以

$$A^4 = I_4$$

答案为1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1